Introduction to Highway Hierarchy
Tony Li
Background
In the real world, we always consider the
following route planning method:
1 Look for a reasonable motorway
2 Drive on motorways to a location close to
the target
3 Drive to the target from the motorway exit
It may be not optimal, but we usually do not
leave the motorway to drive on a faster way
in the city.
Hierarchy
Local
Local Area (also called Neighborhood, N(s))
nodes(and related edges) around a node s
Size of N(s):
All nodes are settled in a fixed
order during a Dijkstra search from s.
The first H settled nodes
(and related edges) belong to
N(s), i.e., |N(s)|=H
Radius:= max{dist(s,t)|t in N(s)}
 N(s):={v|dist(s,v)<=Radius}
Highway
Highway
Nodes and Edges not in the Local Area
Bypassed Node
There are paths consisting of degree-2
nodes. Such nodes could be bypassed by
introducing shortcut edges.
Simplify the network and save the query
time
Core
The sub-graph induced by the set of non-
bypassed nodes (also called core nodes)
and additional shortcut edges
Highway Hierarchy
Step 1 Organize the topology info of a road
network into a well designed multi-level
architecture --- Preprocessing
Step 2 Query the route from source to target
with very high efficiency --- Query
Preprocessing
Determine N(s) for each s
Partial Shortest Path
Tree Construction
Highway Edge
Selection
Highway Network
Contraction
For each s:
Add Highway Edge to Highway
Network of Next Level
Contraction
Bypass the nodes iteratively
Bypassability
Which nodes should be bypassed?
Average degree
Relaxed edges
To avoid the traps
#shortcuts <= c·(InDegree (u)+OutDegree(u))
Radius
Review
Dijkstra
Settle H nodes (H
L, a param on level L)
Monotony
Weight(u,v)+R(v)>=R(u)
Highway Construction
Review Local and Highway
1 All highway edges of s X
2 highway edges
cross the neighborhood ?
3 Partial Shortest Path Tree
PSPT
To save time, PSPT could not be too large
To keep the connectivity, it should be large
enough
An Edge <u,v> belongs to highway network
iff there are nodes s and t, s.t.
<u,v> is on the canonical shortest path from
s to t && t ! N(s) && s! N(t)
Abort Condition
Abortion Condition : all nodes in the priority
queue are passive.
A node p is passive, iff
PSPT Details
Observations
1 Abortion condition => a(x)+r(x)<weight(x)
2 a(x)=weight(u), u1st node outside N(x)
3 u the grandparent of w, w1st node
outside N(s1)
4 w, weight(w)>b(w)=weight(s1)+R(s1)
PSPT Details
4->3->2->1
1) All nodes are active at the very beginning
2) when s1 is settled, set b(x):=weight(s1)+R(s1)
3) when w is settled(weight(w)>b(x)), set a(x):=
weight(u)
4) when p is settled(weight(x)>a(x)+r(x)), passive
5) nodes succeeding p are passive
PSPT Details
It is ok, if |N(s1) ∩ N(p)|=0
Monotony
Maverick
An active endpoint of a long edge
active && weight(m)>f*(r(s0))
f, balance between preprocessing time and query time
If all active nodes are maverick, search from
passive nodes is no longer continued.
more highway edges
Edge Selection
Edge<u,v> in neither R(s0) nor R(t0) are
Highway edges, where t0 is a leaf node of
PSPT and <u,v> is on path<s0,…,t0>.
Details
Slack and Weight
Weight, distance from s0
Slack, ‘distance’ from the border of N(p)
Backward Evaluation
Edges start from nodes with slack<0 are highway
edges
Terminate if a node has a smaller slack already
Considerations
DAG (Directed Acyclic Graph) vs. PSPT
partial shortest-path directed acyclic(no circle)
graph
edges in red PsPT
edges in red&green DAG
DAG vs. PSPT with Shadows
Considerations
Turn Cost Model
Abort Condition
Monotony X
r(s0)>b’(x)=weight(s1)+turncost(s1)+r(s1)
b(x)=max{r(s0),b’(x)}
Slack
Query
Query
Bidirectional Dijkstra
s t
Bidirectional A*
Query
hierarchies
Query
Preprocessing vs. Query
Routing type(Cost Function) 1 v 4(shorest
vs. fastest)
We have to tune RCM(Road Cost Model)
and improve TCM(Turn Cost Model)
Different RCMs
edgeWeightForSearch/edgeWeightForUpgrade
Different TCMs
no turncost added to
edgeWeightForSearch
delay upgrading
Further Reading
Canonical. Fast and Exact Shortest Path Queries
Using Highway Hierarchies. P16.
Monotony. Engineering Highway Hierarchies. p3
DAG. Route Planning in Road Networks. P41